package com.ting.test.algorithms.前缀树;


/**
 * next数组 一共26个元素，从0到25，每一个下标代表一个字母
 */
public class TrieTree {
    private char base = 'a';
    private NodeWithArray root;

    /**
     * 注意在操作时 root节点只作为跟节点 并不代表任何字母
     */
    public TrieTree() {
        this.root = new NodeWithArray();
    }


    public boolean insert(String word) {
        if (null==word||word.length()<1) {
            return false;
        }
        char[] chars = word.toCharArray();
        NodeWithArray node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            NodeWithArray[] next = node.next;
            if (next[index] == null) {
                next[index] = new NodeWithArray();
            }
            next[index].pass++;
            node = next[index];
        }
        node.end++;
        return true;
    }


    /**
     * 查找字符串是否在线段树中，并返回该字符串被添加过几次
     *
     * @param word
     * @return
     */
    public int search(String word) {
        if (word==null) {
            return 0;
        }
        char[] chars = word.toCharArray();
        NodeWithArray node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            NodeWithArray[] next = node.getNext();
            // 如果字符串嗨没匹配完，但是next数组中没有下一个字符 说明字符串不存在
            if (next[index] == null) {
                return 0;
            }
            node = next[index];
        }
        return node.end;
    }


    public boolean delete(String word) {
        //先判断字符串是否在前缀树中，在才会删除
        if (search(word) == 0) {
            return false;
        }

        char[] chars = word.toCharArray();
        NodeWithArray node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            NodeWithArray[] next = node.next;
            next[index].pass--;
            node = next[index];
        }
        node.end--;
        return true;
    }

    /**
     * 		// 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
     * @param word
     * @return
     */
    public int prefixNumber(String word) {
        if (word==null) {
            return 0;
        }
        char[] chars = word.toCharArray();
        NodeWithArray node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            NodeWithArray[] next = node.getNext();
            // 如果字符串嗨没匹配完，但是next数组中没有下一个字符 说明字符串不存在
            if (next[index] == null) {
                return 0;
            }
            node = next[index];
        }
        return node.pass;
    }


}
